package elementaryAlgorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author 郭辉
 * @className TODO
 * @description 119. 杨辉三角 II
 * 给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。
 *
 * 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
 *
 *
 *
 *
 *
 * 示例 1:
 *
 * 输入: rowIndex = 3
 * 输出: [1,3,3,1]
 * 示例 2:
 *
 * 输入: rowIndex = 0
 * 输出: [1]
 * 示例 3:
 *
 * 输入: rowIndex = 1
 * 输出: [1,1]
 *
 *
 * 提示:
 *
 * 0 <= rowIndex <= 33
 *
 *
 * 进阶：
 *
 * 你可以优化你的算法到 O(rowIndex) 空间复杂度吗？
 * @date 2023/3/14 16:53
 * @company 海康威视
 * @since 1.0.0
 */
public class Leet119 {
    public List<Integer> getRow(int rowIndex) {
        List<List<Integer>> dp = new ArrayList<>(35);
        for (int i = 0; i < 35; i++) {
            List<Integer> list = new ArrayList<>();
            for (int j = 0; j < i; j++) {
                if (j == 0 || j == i-1){
                    list.add(j,1);
                }else {
                    list.add(dp.get(i-1).get(j-1) + dp.get(i-1).get(j));
                }
            }
            dp.add(list);
        }
        return dp.get(rowIndex+1);
    }

    public List<Integer> getRowT(int rowIndex) {
        List<Integer> dp = new ArrayList<>();
        for (int i = 0; i < rowIndex+2; i++) {
            List<Integer> list = new ArrayList<>();
            for (int j = 0; j < i; j++) {
                if (j == 0 || j == i-1){
                    list.add(j,1);
                }else {
                    list.add(dp.get(j-1) + dp.get(j));
                }
            }
            dp.clear();
            dp.addAll(list);
        }
        return dp;
    }

    public static void main(String[] args) {
        Leet119 leet119 = new Leet119();
        System.out.println(leet119.getRowT(0));
    }
}
